1. Technical Field
This relates to the design and manufacture of very large scale integrated (xe2x80x9cVLSIxe2x80x9d) circuits and, more particularly, to a method for routing connections between component tiles of a VLSI circuit suitable for use in conjunction with the design and manufacture of VLSI circuits.
2. Description of the Relevant Art
A VLSI circuit is typically composed of a plurality of generally horizontal layers, each layer having a plurality of generally rectangular shaped components positioned thereon. VLSI circuit designers commonly refer to these generally rectangular shaped components as xe2x80x9ccomponent tilesxe2x80x9d and to the rectangular shaped open spaces that surround the component tiles as xe2x80x9cspace tiles.xe2x80x9d Component tiles that are to be connected on a VLSI circuit are said to form a xe2x80x9cnetxe2x80x9d, while any component tile not connected to a particular net is considered to be an obstruction to that net. Two tiles are said to be xe2x80x9cadjacentxe2x80x9d if they touch along their edges and xe2x80x9coverlappingxe2x80x9d if there is even a single point located within the interior of both tiles. A set of tiles positioned within a routing area is said to be xe2x80x9cmaximalxe2x80x9d if no two tiles are either overlapping or adjacent on their left or right edges.
One step in the design of a VLSI circuit is to select the wire paths that extend through the space tiles to connect the electrically equivalent component tiles that form nets. A current technique used to determine these paths utilizes a tile expansion algorithm. More specifically, clear space around the component tiles forming a net is fractured into maximal space tiles. Adjoining ones of these maximal space tiles are used to define the most efficient tile path between two components. The path of the actual connection between the components, known as the wire path, is then defined as the route through the space tile path from the center of the component source tile to the center of the component destination tile.
The aforementioned technique for selecting the wire paths for a VLSI circuit design suffers from two drawbacks, both of which may add to the cost of VLSI circuits manufactured in accordance with the design. First, if defined in accordance with the above-described manner, a tile path is not necessarily the optimal tile path through the clear space. Second, since the width of a tile path is typically much larger than the width of a wire path, multiple wire paths may exist through a given tile path. If the wire path located within the tile path is arbitrarily selected, the selected wire path is not necessarily the most efficient wire path potentially located within the tile path.
Disclosed herein is a method and associated apparatus for the design and manufacture of VLSI circuit which incorporates therein a method for routing connections between component tiles of the VLSI circuit being designed. In accordance with the disclosed method, maximal component tile and maximal space tile lists are constructed and, from the constructed lists, the maximal component and maximal space tiles are positioned on the routing area(s). Optimal tile path and minimum cost wire path between pins that are CTs to be connected are determined and, utilizing the determined wire path, a VLSI circuit design is generated. The minimum cost path from a starting tile S to a destination tile T is determined by creating a priority queue and a search tree ST with the starting tile S as its root. While the priority queue is not empty, a low cost tile E neighboring the starting tile S is popped and, if a tile path to destination tile T is found, the cost of the tile path is evaluated and saved as the minimum cost point path. Otherwise, for each tile F neighboring the tile E, the search tree is expanded and, for a tile path having an estimated cost greater than the current cost, the search path is pruned. Otherwise, the search is expanded by adding the tile F (with corresponding minimum cost CE)) to the priority queue Q and inserting the tile F into the search tree as a child node of the tile E.